package prefix_sum;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @Description 剑指 Offer II 010. 和为 k 的子数组
 * @Author Firenut
 * @Date 2023-02-05 21:23
 */
public class T010_subarraySum {

    @Test
    public void test() {
        System.out.println(subarraySum(new int[]{1, 1, 1}, 2));
    }

    // 法3:前缀和+hash表优化(推荐！！！)
    // 使用Hash表进行优化(不需要前缀和数组)
    // 对于某一个连续子数组下标从 i...j,该子数组的前缀和为sums[j]-sums[i-1]
    // 当 sums[j]-sums[i-1] == k ===> sums[i-1] == sums[j]-k
    // 也即可以从前缀和数组中判断满足 sums[j]-k 的个数，也即值为sums[i-1]的前缀和个数
    // 如果map 存在sum - k 的key,说明存在某个子数组, 其前缀和为sum - k,假设以j结尾
    // 则说明 j+1...i的子数组,其前缀和为k
    // 可以使用哈希表来保存前缀和以及对应出现的个数,这样判断的时候直接取出个数,时间复杂度是O(1) 从而提高效率
    // 说实话这个没做过是真难想出来的
    // 时间复杂度为O(n) 空间复杂度为O(n)
    public int subarraySum3(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        // 初始化: 前缀和为0的个数是1
        map.put(0, 1);

        int count = 0;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            // sum 表示前i个元素之和
            sum += nums[i];
            // 如果map 存在sum - k的key,说明存在某个子数组,其前缀和为sum - k,假设以j结尾
            // 则说明 j+1...i的子数组,其前缀和为k
            if (map.containsKey(sum - k)) {
                // 当sum=k时,如果没有 map.put(0, 1);
                // 相当于count+=0, 那么会导致结果漏了一个值
                count += map.get(sum - k);
            }

            // 记录前缀和 及其 个数
            // 这里key是 sum,而不是 sum-k
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }


    // 法2:前缀和
    // 前缀和数组,sums[0]置为0是方便后面的运算,比如sums[j+1]-sums[i] 得到的是nums[i] + ... +nums[j]
    // sums[j+1] = nums[1]+nums[2]+...+nums[j] = sums[j]+nums[j]
    // 如果一开始sums[0]==nums[0],当 i==j 的时候就没法通过sums数组得到nums[i],因为他俩相减的结果是0
    // 所以一般前缀和数组的第一个元素sums[0]是置为0的，长度是原数组+1(记死了！)
    // 时间复杂度为O(n^2) 空间复杂度为O(n)
    public int subarraySum2(int[] nums, int k) {
        int[] sums = new int[nums.length + 1];
        /* error:
        for(int i=1;i<nums.length;i++){
            sums[i]=nums[i]+sums[i-1]; // sums[1]=nums[1]+sums[0]
        }
        */
        for (int i = 0; i < nums.length; i++) {
            sums[i + 1] = nums[i] + sums[i];
            //sums[nums.length] = nums[nums.length-1]+ sums[nums.length-1]
        }
        int count = 0;
        for (int i = 0; i < nums.length; i++) { //注意是 nums.length 不是 sums.length,不然后面j+1会越界
            for (int j = i; j < nums.length; j++) {
                // 固定以i开始,判断 以j结尾的前缀和是否等于 k

                //初始值是 j=i 而不是 j=i+1 (当然可以写成j=i+1,循环的条件以及下面的if就要修改了)
                if (sums[j + 1] - sums[i] == k) { // nums[i] + ... +nums[j] (这块确实有点绕...)
                    // sums[j+1]对应nums[0]+...+nums[j]
                    // sums[i]对应  nums[0]+...+nums[i-1]
                    // 所以相减就是nums[i]+...+nums[j],你也可以画图理解一下
                    // 当i==0,j+1==nums.length时,求出的即nums[0]+...+nums[nums.length-1]的和
                    count++;
                }
            }
        }
        return count;
    }

    // 这里也是前缀和，只是比较的条件有些不同
    public int subarraySum2_1(int[] nums, int k) {
        int[] sums = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            sums[i + 1] = nums[i] + sums[i];
        }
        int count = 0;
        for (int i = 0; i < nums.length; i++) { //注意是 nums.length 不是 sums.length,不然后面j=i+1会越界
            for (int j = i + 1; j < sums.length; j++) {  // 这里要改成 sums.length而不是nums.length,不然就取不到sums[sums.length-1]
                if (sums[j] - sums[i] == k) {
                    count++;
                }
            }
        }
        return count;
    }

    // 暴力解法 优化
    public int subarraySum1(int[] nums, int k) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            // 固定i结尾,以j为开头的连续子数组之和
            for (int j = i; j >= 0; j--) {
                sum += nums[j];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }

    // 暴力 未优化
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                int sum = 0;
                for (int t = i; t <= j; t++) {
                    sum += nums[t];
                }
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }

}
